<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            并查集 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">并查集</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-02-02 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>8.9k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>41 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2><p>在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：</p>
<h3 id="UF接口"><a href="#UF接口" class="headerlink" title="UF接口"></a>UF接口</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">interface</span> <span class="title">UF</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>; <span class="comment">//获取并查集的大小</span></span><br><span class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>; <span class="comment">//是否连接</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>; <span class="comment">//合并两个集合</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="UnionFind1-QuickFind"><a href="#UnionFind1-QuickFind" class="headerlink" title="UnionFind1-QuickFind"></a>UnionFind1-QuickFind</h3><p>按照朴素的思路写出的并查集</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UnionFind1</span> <span class="keyword">implements</span> <span class="title">UF</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] id; <span class="comment">//集合ids</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UnionFind1</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        id=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++) &#123;</span><br><span class="line">            id[i]=i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> id.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//p所属的集合ID</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p&lt;<span class="number">0</span> &amp;&amp; p&gt;=id.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;p is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> id[p];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> pID=find(p);</span><br><span class="line">        <span class="keyword">int</span> qID=find(q);</span><br><span class="line">        <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;id.length;i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (id[i]==qID) &#123;</span><br><span class="line">                id[i]=pID;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>初始化的时候每个元素都是不同的集合ID</p>
<p><code>find</code>操作会返回他们所属集合ID，时间复杂度<code>O(1)</code></p>
<p><code>isConnected</code>会判断两个元素的集合ID是不是相同的，时间复杂度也是<code>O(1)</code></p>
<p>而<code>unionElement</code> 合并操作就是遍历整个集合，将集合ID等于其中一个的改成另一个，时间复杂度<code>O(N)</code></p>
<blockquote>
<p>这种方式属于快速查找，但是合并的效率太低了，我们还可以继续优化下</p>
</blockquote>
<h3 id="UnionFind2-QuickUnion"><a href="#UnionFind2-QuickUnion" class="headerlink" title="UnionFind2-QuickUnion"></a>UnionFind2-QuickUnion</h3><p>这一次我们不记录每个元素所属的集合ID，我们记录每个元素的父元素的ID，根节点一样的元素就是一个集合，这样就形成了一颗奇怪的树，由子节点指向父节点的树（森林）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UnionFind2</span> <span class="keyword">implements</span> <span class="title">UF</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UnionFind2</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        parent=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++) &#123;</span><br><span class="line">            parent[i]=i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> parent.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//p所属的集合ID</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">            index=parent[index];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> pID=find(p);</span><br><span class="line">        <span class="keyword">int</span> qID=find(q);</span><br><span class="line">        <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        parent[pID]=qID;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>初始化的时候每个元素的父节点都指向自己</p>
<p><code>find</code>操作的时候就不停的向上爬，找到每个元素的根节点，就是它的集合ID，时间复杂度就是<code>O(h)</code> h是树的高度，注意这里并不是<code>logN</code>，因为这课树并一定是一棵二叉树</p>
<p><code>isConnected</code> 和上面一样，判断两个元素的根节点时候一样就ok</p>
<p><code>unionElement</code> 合并两个元素的集合，我们只需要将其中一个<code>parentID</code>变为另一个的<code>parentID</code>就Ok了，时间复杂度<code>O(hq)+O(hp)</code> (hp，hq代表p和q形成的树的高度)</p>
<blockquote>
<p>相比上面的<code>UnionFInd1</code>我们牺牲了一点查找的效率获得了更高的合并效率，但是仍然还有可以优化的点，我们这里在合并两个集合的时候，并没有考虑两颗树的形状，直接将一颗树加在了另一颗的后面，而这样很有可能会增加合并后的树的高度，甚至可能会形成一个链表的结构，这将极大的影响我们的时间复杂度，所以我们可以考虑更好的合并方式</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/ifSkJmMWNB2U.png?imageslim"
                      alt="mark"
                ></p>
</blockquote>
<h3 id="UnionFind3-size优化"><a href="#UnionFind3-size优化" class="headerlink" title="UnionFind3-size优化"></a>UnionFind3-size优化</h3><p>这里我们添加一个sz数组用来记录每个集合的元素个数</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UnionFind3</span> <span class="keyword">implements</span> <span class="title">UF</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] sz; <span class="comment">//记录每颗树的节点数量</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UnionFind3</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        parent=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        sz=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++) &#123;</span><br><span class="line">            parent[i]=i;</span><br><span class="line">            sz[i]=<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> parent.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//p所属的集合ID</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">            index=parent[index];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> pID=find(p);</span><br><span class="line">        <span class="keyword">int</span> qID=find(q);</span><br><span class="line">        <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (sz[pID]&gt;sz[qID]) &#123;</span><br><span class="line">            parent[qID]=pID;</span><br><span class="line">            sz[pID]+=sz[qID];    </span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            parent[pID]=qID;</span><br><span class="line">            sz[qID]+=sz[pID];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>初始化的时候额外的将每个元素的sz置为1</p>
<p><code>find</code>操作和<code>isConnected</code>没有变化</p>
<p><code>unionElement</code> 的时候我们不在是盲目的随意合并，而是将size小的集合加在size大的集合下</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/ifSkJmMWNB2U.png?imageslim"
                      alt="mark"
                ></p>
<p>类似这样的情况下就不会将1接在5下面，而是将5接在1下面，这样合并后的集合的高度就不会增大</p>
<blockquote>
<p>但是根据size判断一定能准确判断么？很显然是不行的</p>
</blockquote>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/SdfeawuEf9Qz.png?imageslim"
                      alt="mark"
                ></p>
<p>类似这样的，如果按照之前的按照size合并的方案可能反而会导致树的高度增加，所以更加合理的方案应该是根据树的高度来合并</p>
<h3 id="UnionFind4-hight优化"><a href="#UnionFind4-hight优化" class="headerlink" title="UnionFind4-hight优化"></a>UnionFind4-hight优化</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UnionFind4</span> <span class="keyword">implements</span> <span class="title">UF</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] hight; <span class="comment">//每个集合形成的树的高度</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UnionFind4</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        parent=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        hight=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++) &#123;</span><br><span class="line">            parent[i]=i;</span><br><span class="line">            hight[i]=<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> parent.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//p所属的集合ID</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">            index=parent[index];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> pID=find(p);</span><br><span class="line">        <span class="keyword">int</span> qID=find(q);</span><br><span class="line">        <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (hight[pID]&gt;hight[qID]) &#123;</span><br><span class="line">            parent[qID]=pID;    </span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(hight[pID]&lt;hight[qID])&#123;</span><br><span class="line">            parent[pID]=qID;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123; <span class="comment">//高度相等情况,才会增大树的高度</span></span><br><span class="line">            parent[pID]=qID; </span><br><span class="line">            hight[qID]++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>初始化的时候仍然将每个元素的高度设置为1</p>
<p>合并的时候我们根据树的高度来合并，将高度小的集合添加到高度大的集合上，这样整体的高度并不会变化，仍然是高度较大的集合的高度，只有在两颗树的高度相同的时候才会使集合高度增加，这个时候就无所谓谁添加到谁上了</p>
<blockquote>
<p>回头想一想，其实我们查找或者合并的时候并不会去关系每个元素的父节点又或者爷节点是啥，我们只关心的是这个元素的祖宗节点是啥，也就是根节点是啥，也就是我们希望每个集合的高度越小越好</p>
</blockquote>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/D84lWwYGlVag.png?imageslim"
                      alt="mark"
                ></p>
<h3 id="UnionFind5-路径压缩"><a href="#UnionFind5-路径压缩" class="headerlink" title="UnionFind5-路径压缩"></a>UnionFind5-路径压缩</h3><p>在find过程中增加了路径压缩的功能</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UnionFind5</span> <span class="keyword">implements</span> <span class="title">UF</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] rank;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UnionFind5</span><span class="params">(<span class="keyword">int</span> size)</span></span>&#123;</span><br><span class="line">        parent=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        rank=<span class="keyword">new</span> <span class="keyword">int</span>[size];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;size;i++) &#123;</span><br><span class="line">            parent[i]=i;</span><br><span class="line">            rank[i]=<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getSize</span><span class="params">()</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> parent.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//p所属的集合ID</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">            parent[index]=parent[parent[index]]; <span class="comment">//路径压缩</span></span><br><span class="line">            index=parent[index];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    <span class="comment">//递归的方式进行路径压缩，可以压得更低</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find2</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(parent[index]!=index)&#123;</span><br><span class="line">            parent[index]=find2(parent[index]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> parent[index];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> pID=find(p);</span><br><span class="line">        <span class="keyword">int</span> qID=find(q);</span><br><span class="line">        <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (rank[pID]&gt;rank[qID]) &#123;</span><br><span class="line">            parent[qID]=pID;    </span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(rank[pID]&lt;rank[qID])&#123;</span><br><span class="line">            parent[pID]=qID;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123; <span class="comment">//高度相等情况,才会增大树的Rank</span></span><br><span class="line">            parent[pID]=qID; </span><br><span class="line">            rank[qID]++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>find操作本身就是一个向上遍历的过程，所以我们可以直接再find得过程中去进行路径的压缩</p>
<p>核心的语句就是 <code>parent[index]=parent[parent[index]];</code></p>
<p>如果父节点不是要找的根节点就将父节点设置为父节点的父节点</p>
<p>当然这里还有一种压缩的方式，可以将树压缩的更短，也就是上面的<code>find2</code>，核心语句就是</p>
<p> <code>parent[index]=find2(parent[index])</code> </p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/D84lWwYGlVag.png?imageslim"
                      alt="mark"
                ></p>
<p>如果是这样的树执行 <code>find2(5)</code> 可以直接将树压缩成左边的样子，而<code>find1(5)</code> 并不能一次就压缩成这样，两者各有优缺点，这里不过多阐述</p>
<blockquote>
<p>细心的朋友肯定发现了，我这里将<code>hight</code>改成了<code>rank</code>，为什么要改成rank?</p>
<p>其实原因很简单，在加入了路径压缩后，这里的hight不再能表示高度的含义，所以我们改成了Rank</p>
<p>那我们为什么不继续维护这个高度了？这样不是就无法准确的判断如何合并了嘛？</p>
<p>其实这里如果想要继续维护这个树的高度是一种不太明智的选择，成本太大了，难以维护，并不是简单的<code>--</code> 就可以完成的，会有很多的情况，所以我们索性直接将其改成Rank作为一个参考量，表示这个集合的排名，其实仔细想一想，我们进行路径压缩带来的优化明显会大于维护hight带来的优化</p>
</blockquote>
<h3 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h3><p>这里经过科学家们的计算证明得到最终的时间复杂度是 <code>O(log*N)</code>我也是第一次听说这个复杂度，</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200101/iXPijTwciz0b.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>迭代对数</strong></p>
<table>
<thead>
<tr>
<th>n</th>
<th>lg* n</th>
</tr>
</thead>
<tbody><tr>
<td>(−∞, 1]</td>
<td>0</td>
</tr>
<tr>
<td>(1, 2]</td>
<td>1</td>
</tr>
<tr>
<td>(2, 4]</td>
<td>2</td>
</tr>
<tr>
<td>(4, 16]</td>
<td>3</td>
</tr>
<tr>
<td>(16, 65536]</td>
<td>4</td>
</tr>
<tr>
<td>(65536, 2^65536]</td>
<td>5</td>
</tr>
</tbody></table>
<p>可以看到，时间复杂度是相当低，可以近似的认为就是一个<code>O(1)</code> 常数的复杂度</p>
<h2 id="练手例题"><a href="#练手例题" class="headerlink" title="练手例题"></a>练手例题</h2><h3 id="547-朋友圈"><a href="#547-朋友圈" class="headerlink" title="547. 朋友圈"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/friend-circles/" >547. 朋友圈<i class="fas fa-external-link-alt"></i></a></h3><p>班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。</p>
<p>给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果<code>M[i][j] = 1</code>，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">[[<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>]]</span><br><span class="line">输出: <span class="number">2</span> </span><br><span class="line">说明：已知学生<span class="number">0</span>和学生<span class="number">1</span>互为朋友，他们在一个朋友圈。</span><br><span class="line">第<span class="number">2</span>个学生自己在一个朋友圈。所以返回<span class="number">2</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">[[<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出: <span class="number">1</span></span><br><span class="line">说明：已知学生<span class="number">0</span>和学生<span class="number">1</span>互为朋友，学生<span class="number">1</span>和学生<span class="number">2</span>互为朋友，所以学生<span class="number">0</span>和学生<span class="number">2</span>也是朋友，所以他们三个在一个朋友圈，返回<span class="number">1</span>。</span><br></pre></td></tr></table></figure>

<p><strong>注意：</strong></p>
<ol>
<li>N 在<code>[1,200]</code>的范围内。</li>
<li>对于所有学生，有<code>M[i][i] = 1</code>。</li>
<li>如果有<code>M[i][j] = 1</code>，则有<code>M[j][i] = 1</code>。</li>
</ol>
<p><strong>解法二</strong></p>
<p>这题很久之前做过 <a href="http://imlgw.top/2019/10/10/leetcode-hui-su/#547-%E6%9C%8B%E5%8F%8B%E5%9C%88">LeetCode回溯&amp;递归</a> 当时DFS做的，其实这题应该属于最经典的并查集的题目了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[] rank;</span><br><span class="line"></span><br><span class="line"><span class="comment">//p所属的集合ID</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">        parent[index]=parent[parent[index]];</span><br><span class="line">        index=parent[index];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">unionElement</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pID=find(p);</span><br><span class="line">    <span class="keyword">int</span> qID=find(q);</span><br><span class="line">    <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (rank[pID]&gt;rank[qID]) &#123;</span><br><span class="line">        parent[qID]=pID;    </span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(rank[pID]&lt;rank[qID])&#123;</span><br><span class="line">        parent[pID]=qID;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123; <span class="comment">//高度相等情况,才会增大树的高度</span></span><br><span class="line">        parent[pID]=qID; </span><br><span class="line">        rank[qID]++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findCircleNum</span><span class="params">(<span class="keyword">int</span>[][] M)</span> </span>&#123;</span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[M.length];</span><br><span class="line">    rank=<span class="keyword">new</span> <span class="keyword">int</span>[M.length];</span><br><span class="line">    <span class="comment">//初始化</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;M.length;i++) &#123;</span><br><span class="line">        parent[i]=i;</span><br><span class="line">        rank[i]=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//union</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;M.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;M.length;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (M[i][j]==<span class="number">1</span>) &#123;</span><br><span class="line">                unionElement(i,j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;parent.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (parent[i]==i) &#123;</span><br><span class="line">            res++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>代码还是很简单的，合并之后统计一下数量就ok了</p>
<h3 id="128-最长连续序列"><a href="#128-最长连续序列" class="headerlink" title="128. 最长连续序列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-consecutive-sequence/" >128. 最长连续序列<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个未排序的整数数组，找出最长连续序列的长度。</p>
<p>要求算法的时间复杂度为 <code>O(n)</code>。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">100</span>, <span class="number">4</span>, <span class="number">200</span>, <span class="number">1</span>, <span class="number">3</span>, <span class="number">2</span>]</span><br><span class="line">输出: <span class="number">4</span></span><br><span class="line">解释: 最长连续序列是 [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>]。它的长度为 <span class="number">4</span>。</span><br></pre></td></tr></table></figure>

<p><strong>并查集解法</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//并查集</span></span><br><span class="line">HashMap&lt;Integer,Integer&gt; parent;</span><br><span class="line"></span><br><span class="line">HashMap&lt;Integer,Integer&gt; size;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> max=<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(parent.get(index)!=index)&#123;</span><br><span class="line">        <span class="comment">//parent[index]=parent[parent[index]];</span></span><br><span class="line">        parent.put(index,parent.get(index));</span><br><span class="line">        index=parent.get(index);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pID=find(p);</span><br><span class="line">    <span class="keyword">int</span> qID=find(q);</span><br><span class="line">    <span class="keyword">if</span> (pID==qID) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> pSize=size.get(pID);</span><br><span class="line">    <span class="keyword">int</span> qSize=size.get(qID);</span><br><span class="line">    <span class="keyword">if</span> (pSize &gt; qSize) &#123;</span><br><span class="line">        <span class="comment">//parent[qID]=pID;</span></span><br><span class="line">        parent.put(qID,pID);</span><br><span class="line">        <span class="comment">//size[pID]+=size[qID];</span></span><br><span class="line">        size.put(pID,pSize+qSize);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="comment">//parent[pID]=qID;</span></span><br><span class="line">        parent.put(pID,qID);</span><br><span class="line">        <span class="comment">//size[qID]+=size[pID];</span></span><br><span class="line">        size.put(qID,pSize+qSize);</span><br><span class="line">    &#125;</span><br><span class="line">    max=Math.max(max,pSize+qSize); <span class="comment">//统计最大值</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">initUnionFind</span><span class="params">(<span class="keyword">int</span>[]nums)</span></span>&#123;</span><br><span class="line">    parent=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    size=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        parent.put(nums[i],nums[i]);</span><br><span class="line">        size.put(nums[i],<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestConsecutive</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums ==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    HashSet&lt;Integer&gt; set=<span class="keyword">new</span> HashSet();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        set.add(nums[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    initUnionFind(nums);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (set.contains(nums[i]-<span class="number">1</span>)) &#123; <span class="comment">//判断-1或者+1都可以</span></span><br><span class="line">            union(nums[i],nums[i]-<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这里用并查集其实并不是最优解，直接循环用HashSet感觉会更好更简洁  <a href="http://imlgw.top/2019/09/15/leetcode-cha-zhao/">详见 LeetCode查找</a> 不过熟悉一下并查集还是不错的，这里因为是根据num的数值判断的，code所以用数组索引合并是行不通的，需要改成Hash表</p>
<h3 id="1319-连通网络的操作次数"><a href="#1319-连通网络的操作次数" class="headerlink" title="1319. 连通网络的操作次数"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/" >1319. 连通网络的操作次数<i class="fas fa-external-link-alt"></i></a></h3><p>用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。</p>
<p>网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。</p>
<p>给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。 </p>
<p><strong>示例 1：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2020/02/01/4HfDievqKpbswNh.png"
                      alt="image.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">4</span>, connections = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">1</span>,<span class="number">2</span>]]</span><br><span class="line">输出：<span class="number">1</span></span><br><span class="line">解释：拔下计算机 <span class="number">1</span> 和 <span class="number">2</span> 之间的线缆，并将它插到计算机 <span class="number">1</span> 和 <span class="number">3</span> 上</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2020/02/01/mDjJCSHwOrZoa9g.png"
                      alt="image.png"
                ></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">6</span>, connections = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">1</span>,<span class="number">2</span>],[<span class="number">1</span>,<span class="number">3</span>]]</span><br><span class="line">输出：<span class="number">2</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">6</span>, connections = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">0</span>,<span class="number">3</span>],[<span class="number">1</span>,<span class="number">2</span>]]</span><br><span class="line">输出：-<span class="number">1</span></span><br><span class="line">解释：线缆数量不足。</span><br></pre></td></tr></table></figure>


<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：n = <span class="number">5</span>, connections = [[<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">2</span>],[<span class="number">3</span>,<span class="number">4</span>],[<span class="number">2</span>,<span class="number">3</span>]]</span><br><span class="line">输出：<span class="number">0</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= n &lt;= 10^5</li>
<li>1 &lt;= connections.length &lt;= min(n*(n-1)/2, 10^5)</li>
<li>connections[i].length == 2</li>
<li>0 &lt;= connections[i][0], connections[i][1] &lt; n</li>
<li>connections[i][0] != connections[i][1]</li>
<li>没有重复的连接。</li>
<li>两台计算机不会通过多条线缆连接。</li>
</ul>
<p><strong>解法一</strong></p>
<p>1.12周赛的第三题，挺有意思的，当时想了一会儿，然后就直接想到了并查集</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[] parent; <span class="comment">//父ID</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span>[] rank;</span><br><span class="line"></span><br><span class="line"><span class="comment">//p所属的集合ID</span></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (index&lt;<span class="number">0</span> &amp;&amp; index&gt;=parent.length) &#123;</span><br><span class="line">        <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;index is out....&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(parent[index]!=index)&#123;</span><br><span class="line">        parent[index]=parent[parent[index]];</span><br><span class="line">        index=parent[index];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> pID=find(p);</span><br><span class="line">    <span class="keyword">int</span> qID=find(q);</span><br><span class="line">    <span class="keyword">if</span> (qID==pID) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (rank[pID]&gt;rank[qID]) &#123;</span><br><span class="line">        parent[qID]=pID;    </span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(rank[pID]&lt;rank[qID])&#123;</span><br><span class="line">        parent[pID]=qID;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123; <span class="comment">//高度相等情况,才会增大树的高度</span></span><br><span class="line">        parent[pID]=qID; </span><br><span class="line">        rank[qID]++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//判断集合ID是不是一样的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isConnected</span><span class="params">(<span class="keyword">int</span> p,<span class="keyword">int</span> q)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> find(q)==find(p);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">initUF</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    rank=<span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++) &#123;</span><br><span class="line">        parent[i]=i;</span><br><span class="line">        rank[i]=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">makeConnected</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span>[][] connections)</span> </span>&#123;</span><br><span class="line">    initUF(n);</span><br><span class="line">    <span class="keyword">int</span> more=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;connections.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (isConnected(connections[i][<span class="number">0</span>],connections[i][<span class="number">1</span>])) &#123;</span><br><span class="line">            more++; <span class="comment">//多出来的边个数</span></span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            union(connections[i][<span class="number">0</span>],connections[i][<span class="number">1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (parent[i]==i) &#123;</span><br><span class="line">            count++; <span class="comment">//集合个数</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> count-<span class="number">1</span>&lt;=more?count-<span class="number">1</span>:-<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>核心思路就是将元素合并，然后中间求出多出的边，最后判断多出来的边能不能将所有的集合聚合成一个大集合，也就是<code>count-1&lt;=more</code>的时候才可以联通，否则就无法联通</p>
<h3 id="399-除法求值"><a href="#399-除法求值" class="headerlink" title="399. 除法求值"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/evaluate-division/" >399. 除法求值<i class="fas fa-external-link-alt"></i></a></h3><p>给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。</p>
<p>示例 :</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">给定 a / b = <span class="number">2.0</span>, b / c = <span class="number">3.0</span></span><br><span class="line">问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? </span><br><span class="line">返回 [<span class="number">6.0</span>, <span class="number">0.5</span>, -<span class="number">1.0</span>, <span class="number">1.0</span>, -<span class="number">1.0</span> ]</span><br></pre></td></tr></table></figure>

<p>输入为: <code>vector&lt;pair&lt;string, string&gt;&gt; equations, vector&lt;double&gt;&amp; values, vector&lt;pair&lt;string, string&gt;&gt; queries(方程式，方程式结果，问题方程式)</code>， 其中 <code>equations.size() == values.size()</code>，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回<code>vector&lt;double&gt;</code>类型。</p>
<p>基于上述例子，输入如下：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">equations(方程式) = [ [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;b&quot;</span>], [<span class="string">&quot;b&quot;</span>, <span class="string">&quot;c&quot;</span>] ],</span><br><span class="line">values(方程式结果) = [<span class="number">2.0</span>, <span class="number">3.0</span>],</span><br><span class="line">queries(问题方程式) = [ [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;c&quot;</span>], [<span class="string">&quot;b&quot;</span>, <span class="string">&quot;a&quot;</span>], [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;e&quot;</span>], [<span class="string">&quot;a&quot;</span>, <span class="string">&quot;a&quot;</span>], [<span class="string">&quot;x&quot;</span>, <span class="string">&quot;x&quot;</span>] ]. </span><br></pre></td></tr></table></figure>


<p>输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。</p>
<p><strong>解法一</strong></p>
<p>首先弄清楚题目的意思，这题LeetCode上只是mid，其实我感觉如果用并查集做的话就不是mid题了，今天搞了好长时间并查集的解法</p>
<p>首先来一版不带路径压缩的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> HashMap&lt;String,String&gt; parent=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> HashMap&lt;String,Double&gt; quotient=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="comment">//不带路径压缩</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">find</span><span class="params">(String p)</span></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (parent.get(p)!=p) &#123;</span><br><span class="line">        p=parent.get(p);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> p;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">init</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!parent.containsKey(s)) &#123;</span><br><span class="line">        parent.put(s,s);</span><br><span class="line">        quotient.put(s,<span class="number">1.0</span>);   </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(String a,String b,Double value)</span></span>&#123;</span><br><span class="line">    init(a);init(b);</span><br><span class="line">    String fa=find(a); <span class="comment">// a/fa=val[a], b/fb=val[b]</span></span><br><span class="line">    String fb=find(b);</span><br><span class="line">    <span class="keyword">if</span> (fa.equals(fb)) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    parent.put(fa,fb);</span><br><span class="line">    quotient.put(fa,value*(cal(b)/cal(a))); <span class="comment">//cal(a)和cal(b)代表a和b到根节点的总值</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">double</span>[] calcEquation(List&lt;List&lt;String&gt;&gt; equations, <span class="keyword">double</span>[] values, List&lt;List&lt;String&gt;&gt; queries) &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;equations.size();i++) &#123;</span><br><span class="line">        List&lt;String&gt; equation=equations.get(i);</span><br><span class="line">        merge(equation.get(<span class="number">0</span>),equation.get(<span class="number">1</span>),values[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">double</span>[] res=<span class="keyword">new</span> <span class="keyword">double</span>[queries.size()];</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (List&lt;String&gt; query:queries) &#123;</span><br><span class="line">        String a=find(query.get(<span class="number">0</span>));</span><br><span class="line">        String b=find(query.get(<span class="number">1</span>));</span><br><span class="line">        System.out.println(a+<span class="string">&quot; &quot;</span>+b);</span><br><span class="line">        <span class="keyword">if</span> (!parent.containsKey(query.get(<span class="number">0</span>)) || !parent.containsKey(query.get(<span class="number">1</span>)) || !a.equals(b)) &#123;</span><br><span class="line">            res[index++]=-<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//没有路劲压缩,需要遍历整个路劲求积</span></span><br><span class="line">            res[index++]=cal(query.get(<span class="number">0</span>))/cal(query.get(<span class="number">1</span>));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">//计算当前节点到根节点的路径乘积</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">double</span> <span class="title">cal</span><span class="params">(String index)</span></span>&#123;</span><br><span class="line">    <span class="keyword">double</span> res=quotient.get(index);</span><br><span class="line">    <span class="keyword">while</span>(parent.get(index)!=index)&#123;</span><br><span class="line">        index=parent.get(index);</span><br><span class="line">        res*=quotient.get(index);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其实这题我开始想到就是建图然后BFS，并查集我是真没想到，看来还是不够敏锐，不过有一说一并查集的方法确实比较麻烦，特别是带了路径压缩的。</p>
<p>这里我的并查集的方向是</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">a/b=<span class="number">2</span> , b/c=<span class="number">3</span></span><br><span class="line">    </span><br><span class="line">        c  <span class="number">1</span></span><br><span class="line">        ^</span><br><span class="line">        |</span><br><span class="line">        b  <span class="number">3</span></span><br><span class="line">        ^</span><br><span class="line">        |</span><br><span class="line">        a  <span class="number">2</span></span><br></pre></td></tr></table></figure>

<p><code>quotient</code>代表的是<strong>当前节点</strong>是<strong>直接父节点</strong>的多少倍，也就是 <code>A/fatherA</code>  ，重点就是合并两个集合的时候需要注意：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">已知</span><br><span class="line">a / fa = val[a]</span><br><span class="line">b / fb = val[b]</span><br><span class="line">现在我们要合并a，b且 a / b=value</span><br><span class="line">所以我们需要设置 parent[fa]=fb</span><br><span class="line">由于fa父节点发生了变化所以它的值也需要变化,也就是要求 fa/fb的值</span><br><span class="line">val[fa] = fa/fb = a/b * b/fb * fa/a = value * (val[b] / val[a])</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">private</span> HashMap&lt;String,String&gt; parent=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> HashMap&lt;String,Double&gt; quotient=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="comment">//带路径压缩的</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">find</span><span class="params">(String p)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (parent.get(p)!=p) &#123;</span><br><span class="line">        <span class="comment">//需要先保存父亲的值,因为后面压缩后树只有两层,后面*的就是根节点的权值1,是不对的</span></span><br><span class="line">        <span class="comment">//这里可以看看上面的并茶几的方向和值来判断</span></span><br><span class="line">        String f=parent.get(p); </span><br><span class="line">        parent.put(p,find(f));</span><br><span class="line">        <span class="comment">//这样压缩后的子节点才是正确的</span></span><br><span class="line">        quotient.put(p,quotient.get(p)*quotient.get(f));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> parent.get(p);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">init</span><span class="params">(String s)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (!parent.containsKey(s)) &#123;</span><br><span class="line">        parent.put(s,s);</span><br><span class="line">        quotient.put(s,<span class="number">1.0</span>);   </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(String a,String b,Double value)</span></span>&#123;</span><br><span class="line">    init(a);init(b);</span><br><span class="line">    String fa=find(a); <span class="comment">// fa/a=val[a], fb/b=val[b]</span></span><br><span class="line">    String fb=find(b);</span><br><span class="line">    <span class="keyword">if</span> (fa.equals(fb)) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    parent.put(fa,fb);</span><br><span class="line">    quotient.put(fa,value*(quotient.get(b)/quotient.get(a))); </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">double</span>[] calcEquation(List&lt;List&lt;String&gt;&gt; equations, <span class="keyword">double</span>[] values, List&lt;List&lt;String&gt;&gt; queries) &#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;equations.size();i++) &#123;</span><br><span class="line">        List&lt;String&gt; equation=equations.get(i);</span><br><span class="line">        merge(equation.get(<span class="number">0</span>),equation.get(<span class="number">1</span>),values[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">double</span>[] res=<span class="keyword">new</span> <span class="keyword">double</span>[queries.size()];</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (List&lt;String&gt; query:queries) &#123;</span><br><span class="line">        String a=query.get(<span class="number">0</span>);</span><br><span class="line">        String b=query.get(<span class="number">1</span>);</span><br><span class="line">        <span class="keyword">if</span> (!parent.containsKey(a) || !parent.containsKey(b)) &#123;</span><br><span class="line">            res[index++]=-<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//先做路径压缩</span></span><br><span class="line">            res[index++]=find(a).equals(find(b))?quotient.get(a)/quotient.get(b):-<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这里可以看到已经省略了<code>cal</code> 函数计算从当前节点到根节点的总权值积，因为这里路径压缩已经将树压缩到只有两层了，所以并不需要了，既然要压缩到只有两层，这里就只能使用递归来压缩，循环的版本没办法压到只有两层，这里需要注意压缩中值的变化。</p>
<p><strong>解法三</strong></p>
<p>图的解法放到了 <a href="http://imlgw.top/2019/10/01/leetcode-zhan-dui-lie/">栈和队列专题</a> 中了</p>
<h3 id="695-岛屿的最大面积"><a href="#695-岛屿的最大面积" class="headerlink" title="695. 岛屿的最大面积"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/max-area-of-island/" >695. 岛屿的最大面积<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。</p>
<p>找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">[[<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],</span><br><span class="line"> [<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]]</span><br></pre></td></tr></table></figure>


<p>对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。</p>
<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">[[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]]</span><br></pre></td></tr></table></figure>


<p>对于上面这个给定的矩阵, 返回 0。</p>
<p><strong>注意:</strong> 给定的矩阵grid 的长度和宽度都不超过 50</p>
<p><strong>解法一</strong></p>
<p>lc打卡题选了这题，之前用的dfs，这次用并查集实现下</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//补充一个并查集的解法</span></span><br><span class="line"><span class="keyword">int</span>[] parent=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span>[] size=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> fa=find(a);</span><br><span class="line">    <span class="keyword">int</span> fb=find(b);</span><br><span class="line">    <span class="keyword">if</span>(fa==fb) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span>(size[fa]&gt;size[fb])&#123;</span><br><span class="line">        parent[fb]=fa;</span><br><span class="line">        size[fa]+=size[fb];</span><br><span class="line">        max=Math.max(max,size[fa]);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        parent[fa]=fb;</span><br><span class="line">        size[fb]+=size[fa];</span><br><span class="line">        max=Math.max(max,size[fb]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(parent[p]==p) <span class="keyword">return</span> p;</span><br><span class="line">    parent[p]=find(parent[p]);</span><br><span class="line">    <span class="keyword">return</span> parent[p];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxAreaOfIsland</span><span class="params">(<span class="keyword">int</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m=grid.length;</span><br><span class="line">    <span class="keyword">int</span> n=grid[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">//init</span></span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[m*n];</span><br><span class="line">    size=<span class="keyword">new</span> <span class="keyword">int</span>[m*n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m*n;i++)&#123;</span><br><span class="line">        parent[i]=i;</span><br><span class="line">        size[i]=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//1 1 1 1 </span></span><br><span class="line">    <span class="comment">//1 1 1 1</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="comment">//特判一下 hahaha~ 感觉如果不是lc有wacase我还挺难发现这个</span></span><br><span class="line">                max=Math.max(max,<span class="number">1</span>);</span><br><span class="line">                <span class="comment">//和前面,上面的合并</span></span><br><span class="line">                <span class="keyword">if</span>(i&gt;<span class="number">0</span> &amp;&amp; grid[i-<span class="number">1</span>][j]==<span class="number">1</span>) merge(i*n+j,(i-<span class="number">1</span>)*n+j);</span><br><span class="line">                <span class="keyword">if</span>(j&gt;<span class="number">0</span> &amp;&amp; grid[i][j-<span class="number">1</span>]==<span class="number">1</span>) merge(i*n+j,i*n+j-<span class="number">1</span>);  </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="200-岛屿数量"><a href="#200-岛屿数量" class="headerlink" title="200. 岛屿数量"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-islands/" >200. 岛屿数量<i class="fas fa-external-link-alt"></i></a></h3><p>给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。</p>
<p>岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。</p>
<p>此外，你可以假设该网格的四条边均被水包围。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line"><span class="number">11110</span></span><br><span class="line"><span class="number">11010</span></span><br><span class="line"><span class="number">11000</span></span><br><span class="line"><span class="number">00000</span></span><br><span class="line">输出: <span class="number">1</span></span><br></pre></td></tr></table></figure>


<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line"><span class="number">11000</span></span><br><span class="line"><span class="number">11000</span></span><br><span class="line"><span class="number">00100</span></span><br><span class="line"><span class="number">00011</span></span><br><span class="line">输出: <span class="number">3</span></span><br><span class="line">解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>补充一个并查集的写法，手写出来了，但是逻辑出了一点小问题，卡了一会儿</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//复习下并查集</span></span><br><span class="line"><span class="keyword">int</span>[] rank=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span>[] parent=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> a)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(parent[a]==a) <span class="keyword">return</span> a;</span><br><span class="line">    <span class="keyword">return</span> parent[a]=find(parent[a]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> fa=find(a);</span><br><span class="line">    <span class="keyword">int</span> fb=find(b);</span><br><span class="line">    <span class="keyword">if</span>(fa==fb) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span>(rank[fa]&gt;rank[fb])&#123;</span><br><span class="line">        parent[fb]=fa;</span><br><span class="line">        rank[fa]+=rank[fb];</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        parent[fa]=fb;</span><br><span class="line">        rank[fb]+=rank[fa];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numIslands2</span><span class="params">(<span class="keyword">char</span>[][] grid)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(grid==<span class="keyword">null</span> || grid.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> m=grid.length,n=grid[<span class="number">0</span>].length;</span><br><span class="line">    rank=<span class="keyword">new</span> <span class="keyword">int</span>[m*n];</span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[m*n];</span><br><span class="line">    <span class="comment">//init</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">                parent[i*n+j]=i*n+j;</span><br><span class="line">                rank[i*n+j]=<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">                <span class="comment">//和上/左合并</span></span><br><span class="line">                <span class="keyword">if</span>(i&gt;<span class="number">0</span> &amp;&amp; grid[i-<span class="number">1</span>][j]==<span class="string">&#x27;1&#x27;</span>) merge(i*n+j,(i-<span class="number">1</span>)*n+j);</span><br><span class="line">                <span class="keyword">if</span>(j&gt;<span class="number">0</span> &amp;&amp; grid[i][j-<span class="number">1</span>]==<span class="string">&#x27;1&#x27;</span>) merge(i*n+j,i*n+(j-<span class="number">1</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//直接循环parent会有问题,还是老老实实遍历矩阵</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(grid[i][j]==<span class="string">&#x27;1&#x27;</span> &amp;&amp; parent[i*n+j]==i*n+j)&#123;</span><br><span class="line">                res++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="1020-飞地的数量"><a href="#1020-飞地的数量" class="headerlink" title="1020. 飞地的数量"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-enclaves/" >1020. 飞地的数量<i class="fas fa-external-link-alt"></i></a></h3><p>给出一个二维数组 <code>A</code>，每个单元格为 0（代表海）或 1（代表陆地）。</p>
<p>移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。</p>
<p>返回网格中<strong>无法</strong>在任意次数的移动中离开网格边界的陆地单元格的数量。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]]</span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释： </span><br><span class="line">有三个 <span class="number">1</span> 被 <span class="number">0</span> 包围。一个 <span class="number">1</span> 没有被包围，因为它在边界上。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[[<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">0</span>]]</span><br><span class="line">输出：<span class="number">0</span></span><br><span class="line">解释：</span><br><span class="line">所有 <span class="number">1</span> 都在边界上或可以到达边界。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= A.length &lt;= 500</code></li>
<li><code>1 &lt;= A[i].length &lt;= 500</code></li>
<li><code>0 &lt;= A[i][j] &lt;= 1</code></li>
<li>所有行的大小都相同</li>
</ol>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//并查集</span></span><br><span class="line"><span class="keyword">int</span>[] rank=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span>[] parent=<span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> a)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(parent[a]==a) <span class="keyword">return</span> a;</span><br><span class="line">    <span class="keyword">return</span> parent[a]=find(parent[a]); <span class="comment">//路径压缩</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> fa=find(a);</span><br><span class="line">    <span class="keyword">int</span> fb=find(b);</span><br><span class="line">    <span class="keyword">if</span>(fa==fb) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span>(rank[fa]&gt;rank[fb])&#123;</span><br><span class="line">        parent[fb]=fa;</span><br><span class="line">        rank[fa]+=rank[fb];</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        parent[fa]=fb;</span><br><span class="line">        rank[fb]+=rank[fa];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numEnclaves2</span><span class="params">(<span class="keyword">int</span>[][] A)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(A==<span class="keyword">null</span> || A.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> m=A.length,n=A[<span class="number">0</span>].length;</span><br><span class="line">    rank=<span class="keyword">new</span> <span class="keyword">int</span>[m*n+<span class="number">1</span>];</span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[m*n+<span class="number">1</span>];</span><br><span class="line">    <span class="comment">//init</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(A[i][j]==<span class="number">1</span>)&#123;</span><br><span class="line">                parent[i*n+j]=i*n+j;</span><br><span class="line">                rank[i*n+j]=<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//将边界和虚拟节点合并</span></span><br><span class="line">    <span class="keyword">int</span> dummyNode=m*n;</span><br><span class="line">    parent[dummyNode]=dummyNode;</span><br><span class="line">    rank[dummyNode]=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(A[i][j]==<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="keyword">if</span>(i==<span class="number">0</span> || j==<span class="number">0</span> || i==m-<span class="number">1</span> || j==n-<span class="number">1</span>)&#123;</span><br><span class="line">                    merge(dummyNode,i*n+j);</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123; </span><br><span class="line">                    <span class="comment">//和周围节点合并(一开始复制的上面的，只和左上的合并，结果出bug了hahaha</span></span><br><span class="line">                    <span class="keyword">if</span>(A[i][j-<span class="number">1</span>]==<span class="number">1</span>) merge(i*n+j,i*n+j-<span class="number">1</span>);</span><br><span class="line">                    <span class="keyword">if</span>(A[i-<span class="number">1</span>][j]==<span class="number">1</span>) merge(i*n+j,(i-<span class="number">1</span>)*n+j);</span><br><span class="line">                    <span class="keyword">if</span>(A[i][j+<span class="number">1</span>]==<span class="number">1</span>) merge(i*n+j,i*n+j+<span class="number">1</span>);</span><br><span class="line">                    <span class="keyword">if</span>(A[i+<span class="number">1</span>][j]==<span class="number">1</span>) merge(i*n+j,(i+<span class="number">1</span>)*n+j);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> dump=find(dummyNode);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;m;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;n;j++) &#123;</span><br><span class="line">            <span class="comment">//判断和虚节点是否连接</span></span><br><span class="line">            <span class="keyword">if</span>(A[i][j]==<span class="number">1</span> &amp;&amp; find(i*n+j)!=dump)&#123;</span><br><span class="line">                res++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="990-等式方程的可满足性"><a href="#990-等式方程的可满足性" class="headerlink" title="990. 等式方程的可满足性"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/satisfiability-of-equality-equations/" >990. 等式方程的可满足性<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 <code>equations[i]</code> 的长度为 <code>4</code>，并采用两种不同的形式之一：<code>&quot;a==b&quot;</code> 或 <code>&quot;a!=b&quot;</code>。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。</p>
<p>只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 <code>true</code>，否则返回 <code>false</code>。 </p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;a==b&quot;</span>,<span class="string">&quot;b!=a&quot;</span>]</span><br><span class="line">输出：<span class="keyword">false</span></span><br><span class="line">解释：如果我们指定，a = <span class="number">1</span> 且 b = <span class="number">1</span>，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输出：[<span class="string">&quot;b==a&quot;</span>,<span class="string">&quot;a==b&quot;</span>]</span><br><span class="line">输入：<span class="keyword">true</span></span><br><span class="line">解释：我们可以指定 a = <span class="number">1</span> 且 b = <span class="number">1</span> 以满足满足这两个方程。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;a==b&quot;</span>,<span class="string">&quot;b==c&quot;</span>,<span class="string">&quot;a==c&quot;</span>]</span><br><span class="line">输出：<span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;a==b&quot;</span>,<span class="string">&quot;b!=c&quot;</span>,<span class="string">&quot;c==a&quot;</span>]</span><br><span class="line">输出：<span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 5：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;c==c&quot;</span>,<span class="string">&quot;b==d&quot;</span>,<span class="string">&quot;x!=z&quot;</span>]</span><br><span class="line">输出：<span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= equations.length &lt;= 500</code></li>
<li><code>equations[i].length == 4</code></li>
<li><code>equations[i][0]</code> 和 <code>equations[i][3]</code> 是小写字母</li>
<li><code>equations[i][1]</code> 要么是 <code>&#39;=&#39;</code>，要么是 <code>&#39;!&#39;</code></li>
<li><code>equations[i][2]</code> 是 <code>&#39;=&#39;</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>2020.6.8打卡题，在群里看见了讨论说并查集，所以直接就想到了并查集的做法，自己想的话emmm，感觉也能想到，也不是很复杂的并查集</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//路径压缩+按秩合并</span></span><br><span class="line"><span class="keyword">int</span>[] parent;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span>[] rank;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(parent[p]==p) <span class="keyword">return</span> p;</span><br><span class="line">    <span class="keyword">return</span> parent[p]=find(parent[p]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> af=find(a);</span><br><span class="line">    <span class="keyword">int</span> bf=find(b);</span><br><span class="line">    <span class="keyword">if</span>(af==bf) <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span>(rank[af]&gt;rank[bf])&#123;</span><br><span class="line">        parent[bf]=af;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(rank[af]&lt;rank[bf])&#123;</span><br><span class="line">        parent[af]=bf;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        parent[af]=bf;</span><br><span class="line">        rank[bf]++;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">equationsPossible</span><span class="params">(String[] equations)</span> </span>&#123;</span><br><span class="line">    parent=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">128</span>]; <span class="comment">//-&#x27;a&#x27;减来减去太麻烦了,直接设个128完事</span></span><br><span class="line">    rank=<span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">128</span>];</span><br><span class="line">    <span class="comment">//排序后先合并==,再判断!= 偷懒的做法</span></span><br><span class="line">    <span class="comment">//Arrays.sort(equations,(s1,s2)-&gt;s2.charAt(1)-s1.charAt(1));</span></span><br><span class="line">    <span class="keyword">for</span> (String eq:equations) &#123;</span><br><span class="line">        parent[eq.charAt(<span class="number">0</span>)]=eq.charAt(<span class="number">0</span>);</span><br><span class="line">        rank[eq.charAt(<span class="number">0</span>)]=<span class="number">1</span>;</span><br><span class="line">        parent[eq.charAt(<span class="number">3</span>)]=eq.charAt(<span class="number">3</span>);</span><br><span class="line">        rank[eq.charAt(<span class="number">3</span>)]=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (String eq:equations) &#123;</span><br><span class="line">        <span class="keyword">if</span>(eq.charAt(<span class="number">1</span>)==<span class="string">&#x27;=&#x27;</span>)&#123;</span><br><span class="line">            merge(eq.charAt(<span class="number">0</span>),eq.charAt(<span class="number">3</span>));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (String eq:equations) &#123;</span><br><span class="line">        <span class="keyword">if</span>(eq.charAt(<span class="number">1</span>)==<span class="string">&#x27;!&#x27;</span> &amp;&amp; find(eq.charAt(<span class="number">0</span>))==find(eq.charAt(<span class="number">3</span>)))&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="684-冗余连接"><a href="#684-冗余连接" class="headerlink" title="684. 冗余连接"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/redundant-connection/" >684. 冗余连接<i class="fas fa-external-link-alt"></i></a></h3><p>Difficulty: <strong>中等</strong></p>
<p>在本问题中, 树指的是一个连通且无环的<strong>无向</strong>图。</p>
<p>输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。</p>
<p>结果图是一个以<code>边</code>组成的二维数组。每一个<code>边</code>的元素是一对<code>[u, v]</code> ，满足 <code>u &lt; v</code>，表示连接顶点<code>u</code> 和<code>v</code>的<strong>无向</strong>图的边。</p>
<p>返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 <code>[u, v]</code> 应满足相同的格式 <code>u &lt; v</code>。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入: [[1,2], [1,3], [2,3]]</span><br><span class="line">输出: [2,3]</span><br><span class="line">解释: 给定的无向图为:</span><br><span class="line">  1</span><br><span class="line"> / \</span><br><span class="line">2 - 3</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]</span><br><span class="line">输出: [1,4]</span><br><span class="line">解释: 给定的无向图为:</span><br><span class="line">5 - 1 - 2</span><br><span class="line">    |   |</span><br><span class="line">    4 - 3</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ul>
<li>  输入的二维数组大小在 3 到 1000。</li>
<li>  二维数组中的整数在1到N之间，其中N是输入数组的大小。</li>
</ul>
<p><strong>更新(2017-09-26):</strong><br>我们已经重新检查了问题描述及测试用例，明确图是_<strong>无向 **_图。对于有向图详见</strong>。**对于造成任何不便，我们深感歉意。</p>
<p><strong>解法一</strong></p>
<p>没啥好说的，题目意思读懂就行了</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="keyword">var</span> parent []<span class="keyword">int</span></span><br><span class="line">​</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">union</span><span class="params">(a <span class="keyword">int</span>, b <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    pa := find(a)</span><br><span class="line">    pb := find(b)</span><br><span class="line">    <span class="keyword">if</span> pa == pb &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">    parent[pa] = pb</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;</span><br><span class="line">​</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">find</span><span class="params">(a <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> parent[a] == a &#123;</span><br><span class="line">        <span class="keyword">return</span> a</span><br><span class="line">    &#125;</span><br><span class="line">    parent[a] = find(parent[a])</span><br><span class="line">    <span class="keyword">return</span> parent[a]</span><br><span class="line">&#125;</span><br><span class="line">​</span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">findRedundantConnection</span><span class="params">(edges [][]<span class="keyword">int</span>)</span> []<span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> n = <span class="built_in">len</span>(edges)</span><br><span class="line">    parent = <span class="built_in">make</span>([]<span class="keyword">int</span>, n+<span class="number">1</span>)</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt;= n; i++ &#123;</span><br><span class="line">        parent[i] = i</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; n; i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> !union(edges[i][<span class="number">0</span>], edges[i][<span class="number">1</span>]) &#123;</span><br><span class="line">            <span class="keyword">return</span> edges[i]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> []<span class="keyword">int</span>&#123;&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="685-冗余连接-II"><a href="#685-冗余连接-II" class="headerlink" title="685. 冗余连接 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/redundant-connection-ii/" >685. 冗余连接 II<i class="fas fa-external-link-alt"></i></a></h3><p>Difficulty: <strong>困难</strong></p>
<p>在本问题中，有根树指满足以下条件的<strong>有向</strong>图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。</p>
<p>输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。</p>
<p>结果图是一个以<code>边</code>组成的二维数组。 每一个<code>边</code> 的元素是一对 <code>[u, v]</code>，用以表示<strong>有向</strong>图中连接顶点 <code>u</code> 和顶点 <code>v</code> 的边，其中 <code>u</code> 是 <code>v</code> 的一个父节点。</p>
<p>返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">2</span>], [<span class="number">1</span>,<span class="number">3</span>], [<span class="number">2</span>,<span class="number">3</span>]]</span><br><span class="line">输出: [<span class="number">2</span>,<span class="number">3</span>]</span><br><span class="line">解释: 给定的有向图如下:</span><br><span class="line">  <span class="number">1</span></span><br><span class="line"> / \</span><br><span class="line">v   v</span><br><span class="line"><span class="number">2</span>--&gt;<span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">2</span>], [<span class="number">2</span>,<span class="number">3</span>], [<span class="number">3</span>,<span class="number">4</span>], [<span class="number">4</span>,<span class="number">1</span>], [<span class="number">1</span>,<span class="number">5</span>]]</span><br><span class="line">输出: [<span class="number">4</span>,<span class="number">1</span>]</span><br><span class="line">解释: 给定的有向图如下:</span><br><span class="line"><span class="number">5</span> &lt;- <span class="number">1</span> -&gt; <span class="number">2</span></span><br><span class="line">     ^    |</span><br><span class="line">     |    v</span><br><span class="line">     <span class="number">4</span> &lt;- <span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ul>
<li>  二维数组大小的在3到1000范围内。</li>
<li>  二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。</li>
</ul>
<p><strong>解法一</strong></p>
<p>没做出来，看的题解，感觉怪怪的</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="keyword">var</span> parent []<span class="keyword">int</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">union</span><span class="params">(a <span class="keyword">int</span>, b <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    pa := find(a)</span><br><span class="line">    pb := find(b)</span><br><span class="line">    <span class="keyword">if</span> pa == pb &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">    parent[pa] = pb</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">find</span><span class="params">(a <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> parent[a] == a &#123;</span><br><span class="line">        <span class="keyword">return</span> a</span><br><span class="line">    &#125;</span><br><span class="line">    parent[a] = find(parent[a])</span><br><span class="line">    <span class="keyword">return</span> parent[a]</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">judge</span><span class="params">(edges [][]<span class="keyword">int</span>, k <span class="keyword">int</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    parent = <span class="built_in">make</span>([]<span class="keyword">int</span>, <span class="built_in">len</span>(edges)+<span class="number">1</span>)</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt;= <span class="built_in">len</span>(edges); i++ &#123;</span><br><span class="line">        parent[i] = i</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">0</span>; i &lt; <span class="built_in">len</span>(edges); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> i == k &#123;</span><br><span class="line">            <span class="keyword">continue</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> !union(edges[i][<span class="number">0</span>], edges[i][<span class="number">1</span>]) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">findRedundantDirectedConnection</span><span class="params">(edges [][]<span class="keyword">int</span>)</span> []<span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> n = <span class="built_in">len</span>(edges)</span><br><span class="line">    <span class="keyword">var</span> indegree = <span class="built_in">make</span>([]<span class="keyword">int</span>, n+<span class="number">1</span>)</span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt;= n; i++ &#123;</span><br><span class="line">        indegree[edges[i<span class="number">-1</span>][<span class="number">1</span>]]++</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := n<span class="number">-1</span>; i &gt;= <span class="number">0</span>; i-- &#123;</span><br><span class="line">        <span class="keyword">if</span> indegree[edges[i][<span class="number">1</span>]] == <span class="number">2</span> &#123;</span><br><span class="line">            <span class="comment">//删除该边</span></span><br><span class="line">            <span class="keyword">if</span> judge(edges, i) &#123;</span><br><span class="line">                <span class="keyword">return</span> edges[i]</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> i := n<span class="number">-1</span>; i &gt;= <span class="number">0</span>; i-- &#123;</span><br><span class="line">        <span class="keyword">if</span> indegree[edges[i][<span class="number">1</span>]] == <span class="number">1</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> judge(edges, i) &#123;</span><br><span class="line">                <span class="keyword">return</span> edges[i]</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> []<span class="keyword">int</span>&#123;&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="未完待续"><a href="#未完待续" class="headerlink" title="未完待续"></a>未完待续</h3><p>其实之前做的一些题都可以用并查集做，像<a href="">岛屿数量</a>，<a href="">岛屿最大面积</a>啥的，这里就不多写了，都差不多</p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：并查集</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-02-02 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/02/02/c517589e/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/05/13/2da0528d/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">KMP算法</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/01/21/a91acf16/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">LeetCode贪心</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/02/02/c517589e/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="nav-number">1.</span> <span class="nav-text">并查集</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#UF%E6%8E%A5%E5%8F%A3"><span class="nav-number">1.1.</span> <span class="nav-text">UF接口</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UnionFind1-QuickFind"><span class="nav-number">1.2.</span> <span class="nav-text">UnionFind1-QuickFind</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UnionFind2-QuickUnion"><span class="nav-number">1.3.</span> <span class="nav-text">UnionFind2-QuickUnion</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UnionFind3-size%E4%BC%98%E5%8C%96"><span class="nav-number">1.4.</span> <span class="nav-text">UnionFind3-size优化</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UnionFind4-hight%E4%BC%98%E5%8C%96"><span class="nav-number">1.5.</span> <span class="nav-text">UnionFind4-hight优化</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#UnionFind5-%E8%B7%AF%E5%BE%84%E5%8E%8B%E7%BC%A9"><span class="nav-number">1.6.</span> <span class="nav-text">UnionFind5-路径压缩</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="nav-number">1.7.</span> <span class="nav-text">时间复杂度</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BB%83%E6%89%8B%E4%BE%8B%E9%A2%98"><span class="nav-number">2.</span> <span class="nav-text">练手例题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#547-%E6%9C%8B%E5%8F%8B%E5%9C%88"><span class="nav-number">2.1.</span> <span class="nav-text">547. 朋友圈</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#128-%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E5%BA%8F%E5%88%97"><span class="nav-number">2.2.</span> <span class="nav-text">128. 最长连续序列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1319-%E8%BF%9E%E9%80%9A%E7%BD%91%E7%BB%9C%E7%9A%84%E6%93%8D%E4%BD%9C%E6%AC%A1%E6%95%B0"><span class="nav-number">2.3.</span> <span class="nav-text">1319. 连通网络的操作次数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#399-%E9%99%A4%E6%B3%95%E6%B1%82%E5%80%BC"><span class="nav-number">2.4.</span> <span class="nav-text">399. 除法求值</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#695-%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF"><span class="nav-number">2.5.</span> <span class="nav-text">695. 岛屿的最大面积</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#200-%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F"><span class="nav-number">2.6.</span> <span class="nav-text">200. 岛屿数量</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1020-%E9%A3%9E%E5%9C%B0%E7%9A%84%E6%95%B0%E9%87%8F"><span class="nav-number">2.7.</span> <span class="nav-text">1020. 飞地的数量</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#990-%E7%AD%89%E5%BC%8F%E6%96%B9%E7%A8%8B%E7%9A%84%E5%8F%AF%E6%BB%A1%E8%B6%B3%E6%80%A7"><span class="nav-number">2.8.</span> <span class="nav-text">990. 等式方程的可满足性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#684-%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5"><span class="nav-number">2.9.</span> <span class="nav-text">684. 冗余连接</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#685-%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5-II"><span class="nav-number">2.10.</span> <span class="nav-text">685. 冗余连接 II</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9C%AA%E5%AE%8C%E5%BE%85%E7%BB%AD"><span class="nav-number">2.11.</span> <span class="nav-text">未完待续</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
